package org.lintcode_blind75;

import org.suanfaTranning.ST200_Chatpter1_LineTable_HashTable_String.array.Solution1;

/**
 * @Auther: qingle
 * @Date: 2024/9/9-23:24
 * @Description:描述
 * 给定一个整数数组，找到一个具有最大和的子数组，返回其最大和。
 * 每个子数组的数字在数组中的位置应该是连续的。
 * 输入： [-2,1,-3,4,-1,2,1,-5,4]
 * 输出： 6
 * @version: 1.0
 */
public class O1_MaxSubArray {

	public int maxSubArray(int[] nums) {
		if(nums == null || nums.length == 0) {
			return 0;
		}

		int maxSoFar = nums[0]; // 存储全局最大和
		int maxEndingHere = nums[0]; // 存储局部最大和

		for (int i = 0; i < nums.length; i++) {
			maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
			maxSoFar = Math.max(maxSoFar, maxEndingHere);
		}

		return maxSoFar;
	}

	public static void main(String[] args) {

		O1_MaxSubArray o1_MaxSubArray = new O1_MaxSubArray();
		int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
		System.out.println(o1_MaxSubArray.maxSubArray(nums)); // 输出 6

	}
}
